The present invention relates generally to memory systems and, more particularly, optimizing the translation of virtual addresses into physical addresses using a pipeline implementation for least recently used pointer.
Modern computer graphics applications require high-speed processing in order to generate realistic images on a display device (e.g., a computer monitor). Within a computer, the requisite processing power for modern graphics applications is provided by a host processor and a graphics controller. Large blocks of data and other information must travel to, from, and between the host processor and the graphics controller during operation.
With the Accelerated Graphics Port (AGP) architecture, data used by both the graphics controller and the host processor can be stored in system (host) memory. The AGP architecture provides a dedicated, high speed port through which data can be moved between the graphics controller and system memory. The AGP architecture utilizes host paging. As such, blocks of memory with contiguous linear addresses may not be physically contiguous in system memory. Specifically, each linear address corresponds to some location in a xe2x80x9cvirtualxe2x80x9d memory. In the virtual memory, data for certain structures (e.g., texture maps) are stored in contiguous locations. In the physical system memory, however, the data may actually be stored in noncontiguous locations.
Because the host processor and the graphics controller must see data structures as contiguous blocks, the AGP architecture is equipped with core logic to translate the virtual linear addresses into corresponding physical addresses. This translation is accomplished with a memory-based Graphics Address Remapping Table (GART). The GART supports a mapping function between virtual addresses and physical addresses. With this mapping in the AGP architecture, a processing device (e.g., the host controller or the graphics controller) may use a translation look-aside buffer for performing memory accesses.
In general, the translation look-aside buffer functions to temporarily store data and information for performing translations. In an AGP architecture utilizing a memory-based GART, the translation look-aside buffer is initially searched for information which can be used for translation. If the desired information is not found within the translation look-aside buffer, a xe2x80x9cmissxe2x80x9d occurs and the information must be retrieved from main memory.
Various techniques have been previously developed in order to update or replace the data/information stored in a translation look-aside buffer. All of these previously developed techniques suffer from one or more problems. These problems include limited size (storage capacity) for the translation look-aside buffer, limited associativity of the memory in the translation look-aside buffer, and limited frequency of operation for updating or replacing the data/information stored in the translation look-aside buffer.
The disadvantage and problems associated with previously developed techniques have been substantially reduced or eliminated with the present invention.
In accordance with one embodiment of the present invention, a system is provided for optimizing the translation of virtual addresses into physical addresses using a pipeline implementation. The system includes a main memory device operable to store information for translating a virtual address into a physical address. A translation look-aside buffer cache, coupled to the main memory, has a plurality of translation look-aside buffer entries. Each translation look-aside buffer entry is operable to buffer information for use in translating. A least recently used pointer circuit is coupled to the translation look-aside buffer cache. The least recently used pointer circuit is operable to point to a translation look-aside buffer entry buffering information least recently used in the translation look-aside buffer cache.
In accordance with another embodiment of the present invention, a method is provided for optimizing the translation of virtual addresses into physical addresses using a pipeline implementation. The method includes the following steps: buffering information for translating a virtual address into a physical address in a translation look-aside buffer cache having a number of translation look-aside buffer entries; and generating a least recently used pointer for pointing to the translation look-aside buffer entry having information least recently used in the translation look-aside buffer cache.
In accordance with yet another embodiment of the present invention, a translation look-aside buffer circuit is provided for optimizing the translation of virtual addresses into physical addresses using a pipeline implementation. The translation look-aside buffer circuit includes a translation look-aside buffer cache into which an access is made in a first clock cycle. The translation look-aside buffer cache comprises a plurality of translation look-aside buffer entries operable to buffer information for translating between a virtual address and a physical address. A least recently used pointer circuit, coupled to the translation look-aside buffer cache, is operable to point to a translation look-aside buffer entry buffering information least recently used for translation. The least recently used pointer circuit is operable to be updated in a second clock cycle to reflect the access into the translation look-aside buffer cache in the first clock cycle.
A technical advantage of the present invention includes providing a least recently used (LRU) scheme for replacing data/information in a translation look-aside buffer (TLB) of an Accelerated Graphics Port (AGP) architecture utilizing a Graphics Address Remapping Table (GART). Under this scheme, updates to an LRU pointer are pipelined with corresponding accesses to the translation look-aside buffer. That is, with pipelining, processing of any update to an LRU pointer occurs after processing of the corresponding access to the translation look-aside buffer. As such, each update to the LRU pointer may occur at least one clock cycle after the corresponding access to the translation look-aside buffer. By allowing each LRU pointer update to occur in a clock cycle following the one for the corresponding access to the translation look-aside buffer, timing objectives are more readily achieved. With the reduced timing demands, the present invention thus supports full associativity in the translation look-aside buffer. In addition, the present invention allows larger-sized (great capacity) translation look-aside buffers. Furthermore, the present invention enables higher frequency of operation for updating or replacing the data/information stored in the translation look-aside buffer. Accordingly, the present invention optimizes translation of virtual addresses into physical addresses for Graphics Address Remapping Table GART).